#include<stdio.h>
using namespace std;
void Swap(int* p, int* q) {
	int tmp = *p;
	*p = *q;
	*q = tmp;
}
/*
*向下调整算法
* 建小堆
* 前提：左右子数是小堆
* 从root开始，选出leftchild和rightchild中小的那个与root比较，
* 如果child < parent就交换，向下一次反复此操作
*/
void AdjustDown(int* a, int n, int root) {
	int parent = root;
	int child = (parent * 2) + 1;
	while (child < n) {
		if (child + 1 < n && a[child + 1] > a[child]) {
			child += 1;
		}
		if (a[child] > a[parent]) {
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else {
			break;
		}
	}
}

/*
* 如果左右子树不是小堆呢？
* ->倒着从最后一棵非叶子的子树开调
*/
void Heapsort(int* a, int n) {
	for (int i = (n - 2) / 2; i >= 0; i--) {
		AdjustDown(a, n, i);
	}
/*
* 排升序，建大堆
* why? -> 建小堆，第一个已经最小，直接拿出去后剩下的再构成一棵树，
* 此时结构已然全乱，需要再重建堆选次小的数，时间复杂度为O(n^2)
*/
	int end = n - 1;
	while (end > 0) {  
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}
void test() {
	int a[] = { 1,2,3,5,4,6,7,0,8,9 };
	Heapsort(a, sizeof(a) / sizeof(int));
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
		printf("%d ", a[i]);
}

int main() {
	test();
	return 0;
}

/*
* 堆
* 逻辑结构：完全二叉树
* 物理结构：数组
* 
* 通过下标计算父子节点关系
* leftchild  = parent * 2 + 1;
* rightchild = parent * 2 + 2;
* parent = (child - 1) / 2;
* 
* 大堆：parent >= child -> root最大
* 小堆：parent <= child -> root最小
*/
